class Solution {
    unordered_map<char, unordered_set<char>> edges; // 邻接表
    unordered_map<char, int> in; // 统计入度信息
    bool flag; // 处理边界情况, 类似str1 = a, b, c && str2 = a, b
    
public:
    string alienOrder(vector<string>& words) {
        for(auto& str : words) // 初始化入度哈希表
        {
            for(auto& ch : str)
            {
                in[ch] = 0;
            }
        }
        int sz = words.size();
        for(int i = 0; i < sz; ++i) // 建图
        {
            for(int j = i + 1; j < sz; ++j)
            {
                Add(words[i], words[j]);
                if(flag) // 不合法
                    return "";
            }
        }
 
        queue<char> q; // 拓扑排序
        for(auto& [a, b] : in) // 入度为0的点入队列
        {
            if(b == 0)
                q.push(a);
        }
        string ret;
        while(!q.empty())
        {
            char tmp = q.front();
            q.pop();
            ret += tmp;
            for(auto& ch : edges[tmp]) // 度为0的点指向的点的度减1
            {
                if(--in[ch] == 0)
                    q.push(ch);
            }
        }
 
        for(auto& [a, b] : in) // 返回
        {
            if(b != 0)
                return "";
        }
        return ret;
    }
 
    void Add(string& str1, string& str2) // 收集信息
    {
        int sz = min(str1.size(), str2.size()), i = 0;
        for(; i < sz; ++i)
        {
            if(str1[i] != str2[i])
            {
                char a = str1[i], b = str2[i]; // 前大后小
                if(!edges.count(a) || !edges[a].count(b)) // 防止存入重复信息   
                {
                    edges[a].insert(b);  // a -> b
                    in[b]++;
                }
                break;
            }
        }
        if(i == str2.size() && i < str1.size())
            flag = true; // 类似str1 = a, b, c && str2 = a, b
    }
};